package datastructure.book.dp._1_pathway.exercise.first;

public class _1_Solution {
    /**
     * 一个机器人位于一个 m x n网格的左上角
     * 机器人每次只能向下或者向右移动一步。
     * 机器人试图达到网格的右下角
     * 问总共有多少条不同的路径？
     * 例：m = 3, n = 2  结果为 3
     * m = 3, n = 3   结果为 6
     * 1 <= m, n <= 100
     */
    public int uniquePaths(int m, int n) {
        int[][] f = new int[m][n];
        f[0][0] = 1;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (i - 1 >= 0) {
                    f[i][j]+=f[i-1][j];
                }
                if (j - 1 >= 0) {
                    f[i][j]+=f[i][j-1];
                }
            }
        }
        return f[m-1][n-1];
    }

    /**
     * 使用O(n)空间复杂度
     */
    public int uniquePaths2(int m, int n) {
        int[] f = new int[n];
        f[0] = 1;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (j - 1 >= 0) {
                    f[j]+=f[j-1];
                }
            }
        }
        return f[n-1];
    }
}
